package leetcode.Hot100;

import leetcode.TreeNode;

/**
 * @author Cheng Jun
 * Description: 给定一棵二叉树，你需要计算它的直径长度。
 * 一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 * https://leetcode-cn.com/problems/diameter-of-binary-tree/
 * @version 1.0
 * @date 2021/12/4 9:15
 * @see maxDepth#maxDepth1(TreeNode)
 * 二刷
 */
public class diameterOfBinaryTree {

    static int maxDiameter = 0;

    public static void main(String[] args) {
        TreeNode a = new TreeNode(3);
        TreeNode b = new TreeNode(2);
        TreeNode c = new TreeNode(1, b, a);
        System.out.println(diameterOfBinaryTree(c));
    }

    // 定义：node的左节点最大深度 leftDepth， 右节点的最大深度为 rightDepth
    // 节点 node 的直径长度为 (leftDepth + rightDepth)
    static int diameterOfBinaryTree(TreeNode root) {
        depth(root);
        return maxDiameter;
    }

    static int depth(TreeNode node) {
        if (node == null) {
            return 0;
        } else {
            // 表示节点的最大深度（该节点到最深节点的边数）
            int leftDepth = depth(node.left);
            int rightDepth = depth(node.right);
            maxDiameter = Math.max(maxDiameter, leftDepth + rightDepth);
            return Math.max(leftDepth, rightDepth) + 1;
        }
    }


}
